package othello;

import java.util.ArrayList;

public class MiniMax {
	private int searchDepthLimit;
	private long searchTimeLimit;
	private State currentState;
	private ArrayList<Action> legalMoves;
	
	public MiniMax(int depthLimit, long timeLimit){	
		searchDepthLimit = depthLimit;
		searchTimeLimit = timeLimit;
		legalMoves = new ArrayList<Action>();
	}
	
	/** Look for all the valid moves in any given state */
	private ArrayList<Action> actions(State state){
		ArrayList<Action> moves = new ArrayList<Action>();
		for(int i = 0; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				if(state.playerAtPos(i,j)){
					// Look for moves above
					int k = i-1;
					boolean adjacent = false;
					while(k > 0 && state.opponentAtPos(k,j)){
						adjacent = true;
						k--;
					}
					if(adjacent && state.emptyAtPos(k,j)){
						moves.add(new Action(k,j));
					}
					// Look for moves below
					k = i+1;
					adjacent = false;
					while(k < 7 && state.opponentAtPos(k,j)){
						adjacent = true;
						k++;
					}
					if(adjacent && state.emptyAtPos(k,j)){
						moves.add(new Action(k,j));
					}
					// Look for moves to the left
					k = j-1;
					adjacent = false;
					while(k > 0 && state.opponentAtPos(i,k)){
						adjacent = true;
						k--;
					}
					if(adjacent && state.emptyAtPos(i,k)){
						moves.add(new Action(i,k));
					}
					// Look for moves to the right
					k = j+1;
					adjacent = false;
					while(k < 7 && state.opponentAtPos(i,k)){
						adjacent = true;
						k++;
					}
					if(adjacent && state.emptyAtPos(i,k)){
						moves.add(new Action(i,k));
					}
					// Look for moves to the up/left
					k = i-1;
					int l = j-1;
					adjacent = false;
					while(k > 0 && l > 0 && state.opponentAtPos(k,l)){
						adjacent = true;
						k--;
						l--;
					}
					if(adjacent && state.emptyAtPos(k,l)){
						moves.add(new Action(k,l));
					}
					// Look for moves to the up/right
					k = i-1;
					l = j+1;
					adjacent = false;
					while(k > 0 && l < 7 && state.opponentAtPos(k,l)){
						adjacent = true;
						k--;
						l++;
					}
					if(adjacent && state.emptyAtPos(k,l)){
						moves.add(new Action(k,l));
					}
					// Look for moves to the down/right
					k = i+1;
					l = j+1;
					adjacent = false;
					while(k < 7 && l < 7 && state.opponentAtPos(k,l)){
						adjacent = true;
						k++;
						l++;
					}
					if(adjacent && state.emptyAtPos(k,l)){
						moves.add(new Action(k,l));
					}
					// Look for moves to the down/left
					k = i+1;
					l = j-1;
					adjacent = false;
					while(k < 7 && l > 0 && state.opponentAtPos(k,l)){
						adjacent = true;
						k++;
						l--;
					}
					if(adjacent && state.emptyAtPos(k,l)){
						moves.add(new Action(k,l));
					}
				}
			}
		}
		return moves;
	}
	
	/** Place a disk on a copy of a given board/state and return the new state */
	private State result(State state, Action move){
		State newState = state.copy();
		newState.makeMove(move);
		return newState;
	}
	
	/** Check if the maximum search depth is reached */
	private boolean cutoffTest(State state){
		if((state.getDepth() - currentState.getDepth()) >= searchDepthLimit){
			return true;
		}else{
			return false;
		}
	}
	
	/** Evaluates the utility of a given state */
	private int eval(State state){
		int uVal = 0;
		for(int i = 0; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				if(state.playerAtPos(i,j)){
					// If it is a corner position
					if((i==0 && (j==0 || j==7)) || (i==7 && (j==0 || j==7))){
						uVal += 20;
					// If it is a near corner position
					}else if((i==0 && (j==1 || j==6)) || (i==1 && (j==0 || j==7)) || (i==6 && (j==0 || j==7)) || (i==7 && (j==1 || j==6))){
						uVal -= 10;
					// Anywhere else on the board
					}else{
						uVal += 1;
					}
				}else if(state.opponentAtPos(i,j)){
					if((i==0 && (j==0 || j==7)) || (i==7 && (j==0 || j==7))){
						uVal -= 20;
					}else if((i==0 && (j==1 || j==6)) || (i==1 && (j==0 || j==7)) || (i==6 && (j==0 || j==7)) || (i==7 && (j==1 || j==6))){
						uVal += 10;
					}else{
						uVal -= 1;
					}
				}
			}
		}
		return uVal;
	}
	
	/** Used to determine the winner at the end of a game */
	private void score(State state){
		int score = 0;
		for(int i = 0; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				if(state.playerAtPos(i,j)){
					score += 1;
				}else if(state.opponentAtPos(i,j)){
					score -= 1;
				}
			}
		}
		if(score > 0){
			String player = (currentState.getPlayer() == 1) ? "Black" : "White";
			System.out.println(player + " is the winner!");
		}else if(score < 0){
			String player = (currentState.getPlayer() != 1) ? "Black" : "White";
			System.out.println(player + " is the winner!");
		}else if(score == 0){
			System.out.println("It's a draw!");
		}
	}
	
	/** Starts the search for the best possible move 
	 * from current state to a predefined search depth */
	public Action miniMax(State currentState){
		this.currentState = currentState;
		State state = currentState.copy();
		long searchStartTime = System.currentTimeMillis();
		int indexOfAction = 0;
		int miniMaxVal = Integer.MIN_VALUE;
		int minVal = Integer.MIN_VALUE;
		legalMoves = actions(state);
		for(Action a : legalMoves){
			minVal = minValue(result(state, a));
			if(minVal > miniMaxVal){
				miniMaxVal = minVal;
				indexOfAction = legalMoves.indexOf(a);
			}
			if(System.currentTimeMillis() - searchStartTime >= searchTimeLimit){
				System.out.println("Time is up!");
				break;
			}
		}
		// End of game
		if(legalMoves.isEmpty()){
			score(currentState);
		}
		return legalMoves.get(indexOfAction);
	}
	
	/** Part of the minimax algorithm */
	private int maxValue(State state){
		if(cutoffTest(state)){
			return eval(state);
		}
		int uVal = Integer.MIN_VALUE;
		int minVal;
		ArrayList<Action> moves = actions(state);
		for(Action a : moves){
			minVal = minValue(result(state, a));
			uVal = (uVal > minVal) ? uVal : minVal; // <=> uVal=max(uVal,minVal)
		}
		return uVal;
	}
	
	/** Part of the minimax algorithm */
	private int minValue(State state){
		if(cutoffTest(state)){
			return eval(state);
		}
		int uVal = Integer.MAX_VALUE;
		int maxVal;
		ArrayList<Action> moves = actions(state);
		for(Action a : moves){
			maxVal = maxValue(result(state, a));
			uVal = (uVal < maxVal) ? uVal : maxVal; // <=> uVal=min(uVal,maxVal)
		}
		return uVal;
	}
	
	public boolean isLegalMove(String move){
		Action moveTry = currentState.stringToAction(move);
		if (legalMoves.contains(moveTry)){
			return true;
		} else {
			return false;
		}
		
	}
}
